Turbo codes, introduced in early 1990s, can achieve performance very close to the Shannon limit. These codes are now used in various cellular standards, e.g., WCDMA and 1×EV-DV. However, a turbo-decoder based on the a posterior probability APP algorithm is highly complex. Concatenated single-parity check codes are an alternative that offer much reduced decoding complexity, but at the cost of high error floors and sub-optimal performance at low data rates.
It is believed that zigzag codes and concatenated zigzag codes were first introduced in a paper by L. Ping, X. Huang, and N. Phamdo, entitled ZIGZAG CODES AND CONCATENATED ZIGZAG CODES, IEEE Transactions on Information Theory, Vol. 47, No. 2, February 2001, pp. 800-807. The performance of zigzag codes has been asserted as very close to that of Turbo codes (only about 0.5 dB worse, according to the above paper), while the decoding complexity of zigzag codes is significantly lower than that of Turbo codes. By increasing the coding rate one can increase the data rate at the cost of degraded link performance and increased mega-instructions-per-second MIPS requirement (due to larger size of the data block to be decoded). For high data rate systems that use high coding rates, it is desirable to have lower complexity decoding schemes with performance as close to the Turbo codes (and thus the Shannon limit) as possible. Concatenated zigzag codes appear to provide an attractive alternative to Turbo codes in this respect.
Following is an abbreviated description of zigzag codes, as generally presented in the above paper by Li Ping et al. FIG. 1 is a prior art schematic view of information bits and parity bits in a zigzag code. The information bits to be encoded are represented by {d(i,j)}, i=1,2,3, . . . I, j=1,2,3, . . . J. The parity bits are represented by {p(i)}, i=1,2, . . . I. Further, a segment is defined as [p(i−1),d(i,1),d(i,2), . . . d(i,J),p(i)], and is illustrated in FIG. 1 as the bits along one straight line. The parity bits are chosen such that each segment contains even numbers of ones. The code rate is thus J/(J+1).
At the transmitter, the parity bits are computed as follows:
                                          p            ⁡                          (              1              )                                =                                    ∑                              j                =                1                            J                        ⁢                                          d                ⁡                                  (                                      1                    ,                    j                                    )                                            ⁢                                                          ⁢              mod              ⁢                                                          ⁢              2                                      ⁢                                  ⁢                                            p              ⁡                              (                i                )                                      =                                          [                                                                            ∑                                              j                        =                        1                                            J                                        ⁢                                          d                      ⁡                                              (                                                  i                          ,                          j                                                )                                                                              +                                      p                    ⁡                                          (                                              i                        -                        1                                            )                                                                      ]                            ⁢                                                          ⁢              mod              ⁢                                                          ⁢              2                                ,                                          ⁢                                    for              ⁢                                                          ⁢              i                        =            2                    ,          3          ,          ⋯          ⁢                                          ,                      I            .                                              [        1        ]            
Defining a weighting formula for parameters a1, a2, . . . an
            as      ⁢                          ⁢              W        ⁡                  (                                    a              1                        ,            ⋯            ⁢                                                  ,                          a              n                                )                      =                  [                              ∏                          i              =              1                        n                    ⁢                                          ⁢                      sgn            ⁡                          (                              a                i                            )                                      ]            ⁢                        min                      1            ≤            i            ≤            n                          ⁢                                        a            i                                          ,yields the following equations to calculate the MLA's of the parity and information bits, where F[*] is the forward MLA for the bracketed parity bit, B[*] is the backward MLA for the bracketed parity bit, and L[*] is the MLA for the bracketed information bit:F[p(0)]=+∞F[p(i)]={tilde over (p)}(i)+W(F[p(i−1)],{tilde over (d)}(i,1), . . . ,{tilde over (d)}(i,J)), for i=1, . . . ,I  [2]B[p(I)]={tilde over (p)}(I),B[p(i)]={tilde over (p)}(i)+W({tilde over (d)}(i+1,1), . . . ,{tilde over (d)}(i+1,J),B[p(i+1)]), for i=I−1, . . . ,1  [3]L[d(i,j)]={tilde over (d)}(i,j)+W(F[p(i−1)],{tilde over (d)}(i,1), . . . , {tilde over (d)}(i,j−1),{tilde over (d)}(i,J+1), . . . ,{tilde over (d)}(i,J),B[p(i)])   [4]
The prior art zigzag code of FIG. 1 is shown in tabular form at FIGS. 2A-2B, with an additional set of parity codes to show how zigzag codes might be concatenated. FIG. 2A is an I*J size matrix of information bits d(i,j), where I=5 and J=3. FIG. 2B is a column matrix of I rows showing parity bits p(i). Redefining a code sequence as a string (of at least one) information bit d(i,j) terminating with a parity bit p(i), each of the code segments according to the paper by L. Ping et al. are then the rows of the matrix of FIG. 2A followed by the associated parity bit for the relevant value for i. Each code segment is necessarily the same length as all other code segments, which in this example is three information bits and one parity bit, because j=1, 2, 3, . . . J for each code segment.
A concatenated zigzag code is defined by (I,J,K) where K represents the number of encoders used in concatenation, each encoder multiplying the information bit matrix (FIG. 2A) by a separate parity bit matrix (FIG. 2B). The information data block of FIG. 2A (matrix of I rows and J columns, I*J) to be encoded is first passed through a random interleaver. The parity bits, p(i), of this block of data are calculated using equation [1] above, and represented by FIG. 2B. The original information data block of FIG. 2A is now passed through a second random interleaver and a different set of parity bits are computed and interleaved. This concatenation continues for the number of encoders (K) used. Thus a total of K columns of parity bits (each having length I as shown in FIG. 2B) are computed and are transmitted along with the original information data block of FIG. 2A. The number of total transmitted bits is I*(J+K) (I*J is the number of the information bits and I*K is the number of the parity bits). The code rate of a concatenated zigzag code is therefore J/(J+K). Because each of J and K must be non-zero integers, the coding rate for the above described zigzag codes cannot be arbitrarily set in a transmitter with a finite number of encoders. Each code segment is still the same length as all other code segments.
Practical communication systems are usually required to support several different data rates depending on the channel conditions and user preferences. This requires flexible code rates and puncturing schemes along with appropriate decoding algorithms to provide the desired data rates at an acceptable error rate performance. In a paper by K. S. Chan, L. Ping and S. Chan, entitled ADAPTIVE TYPE II HYBRID ARQ SCHEME USING ZIGZAG CODES, Electronics Letters, Vol. 35, No. 24, November 1999, pp. 2102-2104, a method of puncturing concatenated zigzag codes has been proposed which can be used in hybrid automatic repeat-request ARQ systems as well. However, it appears that the approach in the paper by K. S. Chan et al. does not enable an arbitrary rate code. The inventors view the set of available rates by that approach as not sufficiently broad to serve the needs of current telecommunications systems, as the only available rates are J/(J+1), J/(J+2), . . . , J/(J+K).
What is needed in the art is a coding scheme that enables high data rates but that is less computationally expensive than turbo codes. For practical deployment in existing communication infrastructure, such a coding rate should be compatible with various wireless standards already in use around the world.